package algorithms.sort;

import java.util.PriorityQueue;

/**
 * 堆结构，java中优先队列{@link PriorityQueue} 就是堆结构,默认是小根堆
 *
 * 1.堆(完全二叉树)的数组表示法:
 *  数组:[3,5,2,7,1,9,6]
 *  下标: 0 1 2 3 4 5 6
 * 对应完全二叉树(下标表示):
 *         0
 *        /\
 *       1  2
 *      /\  /\
 *     3 4 5  6
 *
 * 2.堆（完全二叉树）结构使用数组存储的关系,i下标：
 *      1.父节点下标：(i-1)/2；
 *      2.左孩子下标：2*i+1；
 *      3.右孩子下标：2*i+2；
 *
 * 3.堆的分类:
 *      大根堆: 每棵子树的最大值都在顶部
 *      小根堆: 每棵子树的最小值都在顶部
 */
public class Heap {
    /** 堆中元素个数 */
    private int heapSize;

    /** 数组长度 */
    private int size;
    /** 数组存储元素 */
    private int[] arr;

    public Heap(int size) {
        this.arr = new int[this.size = size];
        this.heapSize = 0;
    }

    /**
     * 父节点下标: (i-1)/2；
     *
     * @param index
     * @return
     */
    public int parentIndex(int index) {
        return (index - 1) / 2;
    }

    /**
     * 左孩子下标：2*i+1；
     * @param index
     * @return
     */
    public int leftChildIndex(int index) {
        return 2 * index + 1;
    }

    /**
     * 右孩子下标: 2*i+2
     *
     * @param index
     * @return
     */
    public int rightChildIndex(int index) {
        return 2 * index + 2;
    }

    /**
     * 交换元素
     *
     * @return
     */
    public void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    /**
     * 堆插入元素:
     * 思路：当前位置的值与父节点的值比较
     *      若前位置的值大于节点的值，交换值，index来到父节点位置，向上比较，直到根节点位置，完成大根堆化。
     *      若前位置的值小于节点的值，完成大根堆化。
     *
     * @return
     */
    private void heapInsert() {
        // 当前位置的值与父节点的值比较,若前位置的值大于节点的值
        int curr = heapSize - 1;
        while (arr[curr] > arr[parentIndex(curr)]) {
            // 交换当前的值与父节点的值
            swap(arr,curr,parentIndex(curr));
            // 当前值来到父节点,继续比较
            curr = parentIndex(curr);
        }
    }

    /**
     * 从当前位置开始，使自己和孩子大根堆化。
     * 思路：当前位置与自己的最大孩子比较
     *      若当前位置的值小于最大孩子，交换值，index来到最大孩子位置,向下比较，直到没有孩子为止，完成大根堆化
     *      若当前位置的值大于最大孩子，完成大根堆化。
     *
     * @param index
     * @return
     */
    private void heapify(int index) {
        int left = leftChildIndex(index);
        while (left < heapSize) {
            // 获取孩子的最大值的位置
            int lagest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
            // 最大的孩子与自己比较
            lagest = arr[index] > arr[lagest] ? index : lagest;
            // 自己就是最大的完成堆化
            if (lagest == index) {
                break;
            }
            // 交换
            swap(arr,index,lagest);
            // 位置来到交换的孩子处向下继续堆化
            index = lagest;
            left = leftChildIndex(index);
        }
    }

    /**
     * 插入元素
     *
     * @param e
     */
    public void insert(int e) {
        // 添加到最后一位
        arr[heapSize++] = e;
        heapInsert();
    }

    /**
     * 插入元素
     *
     */
    public int remove() {
        if (isEmpty()) {
            throw new RuntimeException("heap is empty");
        }

        // 移除最大的值
        int r = arr[0];
        // 将最后一位元素放到第一个
        arr[0] = arr[heapSize - 1];
        heapSize--;
        // 从头位置开始向下堆化
        heapify(0);
        return r;
    }

    /**
     * 获取堆中的元素个数
     * @return
     */
    public int getHeapSize() {
        return heapSize;
    }

    /**
     * 查看堆是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return heapSize <= 0;
    }

    public static int[] sort(int[] arr) {
        Heap heap = new Heap(arr.length);
        for (int i = 0; i < arr.length; i++) {
            heap.insert(arr[i]);
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = heap.remove();
        }
        return arr;
    }

}
